package com.ilancuo.algorithm.search;

/**
 * 二分法
 * 
 * 前提int数组是升序排列， 推荐冒泡
 * 二分查找又称折半查找，它是一种效率较高的查找方法。
 * 二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的
 * 
 * @author whwei
 * 
 */
public class BinSearch {

	public static void main(String[] args) {
		int[] a = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		System.out.println("递归实现：" + binSearchByRecursion(a, 0, a.length - 1, 6));
		System.out.println("循环实现：" + binSearchByLoop(a, 6));
	}

	/**
	 * 递归实现
	 * 
	 * @param a 排好序的目标数组
	 * @param start 开始位置
	 * @param end 结束位置
	 * @param key 目标数字
	 * @return 目标数字在数组中的位置[-1：没有查到]
	 */
	public static int binSearchByRecursion(int[] a, int start, int end, int key) {
		int mid = (end - start) / 2 + start;
		if (a[mid] == key) {
			return mid;
		}
		if (start >= end) {
			return -1;
		} else if (key > a[mid]) {
			return binSearchByRecursion(a, mid + 1, end, key);
		} else if (key < a[mid]) {
			return binSearchByRecursion(a, start, mid - 1, key);
		}
		return -1;
	}

	/**
	 * 普通循环实现
	 * 
	 * @param a 排好序的目标数组
	 * @param key 目标数字
	 * @return 目标数字在数组中的位置[-1：没有查到]
	 */
	public static int binSearchByLoop(int[] a, int key) {
		int mid = a.length / 2;
		if (key == a[mid]) {
			return mid;
		}
		int start = 0;
		int end = a.length - 1;
		while (start <= end) {
			mid = (end - start) / 2 + start;
			if (key < a[mid]) {
				end = mid - 1;
			} else if (key > a[mid]) {
				start = mid + 1;
			} else {
				return mid;
			}
		}
		return -1;
	}
}